{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Sum of Imbalance Numbers of All Subarrays"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #hash-table #ordered-set"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #哈希表 #有序集合"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: sumImbalanceNumbers"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #所有子数组中不平衡数字之和"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>一个长度为 <code>n</code>&nbsp;下标从 <strong>0</strong>&nbsp;开始的整数数组 <code>arr</code>&nbsp;的 <strong>不平衡数字</strong>&nbsp;定义为，在&nbsp;<code>sarr = sorted(arr)</code>&nbsp;数组中，满足以下条件的下标数目：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>0 &lt;= i &lt; n - 1</code>&nbsp;，和</li>\n",
    "\t<li><code>sarr[i+1] - sarr[i] &gt; 1</code></li>\n",
    "</ul>\n",
    "\n",
    "<p>这里，<code>sorted(arr)</code>&nbsp;表示将数组 <code>arr</code>&nbsp;排序后得到的数组。</p>\n",
    "\n",
    "<p>给你一个下标从 <strong>0</strong>&nbsp;开始的整数数组&nbsp;<code>nums</code>&nbsp;，请你返回它所有&nbsp;<strong>子数组</strong>&nbsp;的&nbsp;<strong>不平衡数字</strong>&nbsp;之和。</p>\n",
    "\n",
    "<p>子数组指的是一个数组中连续一段 <strong>非空</strong>&nbsp;的元素序列。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>nums = [2,3,1,4]\n",
    "<b>输出：</b>3\n",
    "<b>解释：</b>总共有 3 个子数组有非 0 不平衡数字：\n",
    "- 子数组 [3, 1] ，不平衡数字为 1 。\n",
    "- 子数组 [3, 1, 4] ，不平衡数字为 1 。\n",
    "- 子数组 [1, 4] ，不平衡数字为 1 。\n",
    "其他所有子数组的不平衡数字都是 0 ，所以所有子数组的不平衡数字之和为 3 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>nums = [1,3,3,3,5]\n",
    "<b>输出：</b>8\n",
    "<b>解释：</b>总共有 7 个子数组有非 0 不平衡数字：\n",
    "- 子数组 [1, 3] ，不平衡数字为 1 。\n",
    "- 子数组 [1, 3, 3] ，不平衡数字为 1 。\n",
    "- 子数组 [1, 3, 3, 3] ，不平衡数字为 1 。\n",
    "- 子数组 [1, 3, 3, 3, 5] ，不平衡数字为 2 。\n",
    "- 子数组 [3, 3, 3, 5] ，不平衡数字为 1 。\n",
    "- 子数组 [3, 3, 5] ，不平衡数字为 1 。\n",
    "- 子数组 [3, 5] ，不平衡数字为 1 。\n",
    "其他所有子数组的不平衡数字都是 0 ，所以所有子数组的不平衡数字之和为 8 。</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= 1000</code></li>\n",
    "\t<li><code>1 &lt;= nums[i] &lt;= nums.length</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [sum-of-imbalance-numbers-of-all-subarrays](https://leetcode.cn/problems/sum-of-imbalance-numbers-of-all-subarrays/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [sum-of-imbalance-numbers-of-all-subarrays](https://leetcode.cn/problems/sum-of-imbalance-numbers-of-all-subarrays/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[2,3,1,4]', '[1,3,3,3,5]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumImbalanceNumbers(self, nums: List[int]) -> int:\n",
    "        ans, n = 0, len(nums)\n",
    "        for i, x in enumerate(nums):\n",
    "            vis = [False] * (n + 2)\n",
    "            vis[x] = True\n",
    "            cnt = 0\n",
    "            for j in range(i + 1, n):\n",
    "                x = nums[j]\n",
    "                if not vis[x]:\n",
    "                    cnt += 1 - vis[x - 1] - vis[x + 1]\n",
    "                    vis[x] = True\n",
    "                ans += cnt\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumImbalanceNumbers(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        right = [0] * n\n",
    "        idx = [n] * (n + 1)\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            x = nums[i]\n",
    "            right[i] = min(idx[x], idx[x - 1])\n",
    "            idx[x] = i\n",
    "\n",
    "        ans = 0\n",
    "        idx = [-1] * (n + 1)\n",
    "        for i, (x, r) in enumerate(zip(nums, right)):\n",
    "            ans += (i - idx[x - 1]) * (r - i)\n",
    "            idx[x] = i\n",
    "        return ans - n * (n + 1) // 2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumImbalanceNumbers(self, nums: List[int]) -> int:\n",
    "        ans = 0\n",
    "        for i in range(len(nums)):\n",
    "            vis = set()\n",
    "            cnt = 0\n",
    "            vis.add(nums[i])\n",
    "            for j in range(i + 1, len(nums)):\n",
    "                if nums[j] in vis:\n",
    "                    pass\n",
    "                elif nums[j] - 1 not in vis and nums[j] + 1 not in vis:\n",
    "                    cnt += 1\n",
    "                elif nums[j] - 1 in vis and nums[j] + 1 in vis:\n",
    "                    cnt -= 1\n",
    "                else:\n",
    "                    pass\n",
    "                \n",
    "                vis.add(nums[j])\n",
    "\n",
    "                ans += cnt\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumImbalanceNumbers(self, nums: List[int]) -> int:\n",
    "        # 没有想到找与x相近的值可以转换为找是否出现过x,x-1,x+1\n",
    "        ans = 0\n",
    "        n = len(nums)\n",
    "        for i in range(n):\n",
    "            s = set()\n",
    "            s.add(nums[i])\n",
    "            tot = 0\n",
    "            for j in range(i+1,n,1):\n",
    "                if nums[j] not in s:\n",
    "                    if nums[j]+1 in s and nums[j]-1 in s:\n",
    "                        tot -= 1\n",
    "                    elif nums[j]+1 not in s and nums[j]-1 not in s:\n",
    "                        tot += 1\n",
    "                ans += tot\n",
    "                s.add(nums[j])\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumImbalanceNumbers(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        ans=0\n",
    "        \n",
    "        for i in range(n-1):\n",
    "            visited=set()\n",
    "            visited.add(nums[i])\n",
    "            cnt=0\n",
    "            for j in range(i+1,n):\n",
    "                cur=nums[j]\n",
    "                if cur not in visited:\n",
    "                    if cur+1 in visited and cur-1 in visited:\n",
    "                        cnt-=1\n",
    "                    elif cur+1 not in visited and cur-1 not in visited:\n",
    "                        cnt+=1\n",
    "                visited.add(cur)\n",
    "                ans+=cnt\n",
    "                \n",
    "        return ans\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumImbalanceNumbers(self, nums: List[int]) -> int:\n",
    "        ans = 0\n",
    "        n = len(nums)\n",
    "        for i in range(n):\n",
    "            s = set([nums[i]])\n",
    "            cnt = 0\n",
    "            for j in range(i+1, n):\n",
    "                if(nums[j] in s):\n",
    "                    cnt+=1\n",
    "                else:\n",
    "                    if(nums[j]-1 in s):\n",
    "                        cnt+=1\n",
    "                    if(nums[j]+1 in s):\n",
    "                        cnt+=1\n",
    "                ans += j-i-cnt\n",
    "                s.add(nums[j])\n",
    "        return ans\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumImbalanceNumbers(self, nums: list[int]) -> int:\n",
    "        ans, n = 0, len(nums)\n",
    "        for i, x in enumerate(nums):\n",
    "            arr = [False] * (n+2)\n",
    "            arr[x] = True\n",
    "            cnt = 0\n",
    "            for j in range(i+1, n):\n",
    "                x = nums[j]\n",
    "                if not arr[x]:\n",
    "                    cnt -= arr[x-1] + arr[x+1] - 1\n",
    "                    arr[x] = True\n",
    "                ans += cnt\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumImbalanceNumbers(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        count = [0] * (n + 2)\n",
    "        res = 0\n",
    "        imbalance = -1\n",
    "        left, right = 0, n\n",
    "        while left < right:\n",
    "            for i in range(left, right):\n",
    "                x = nums[i]\n",
    "                count[x] += 1\n",
    "                if count[x] == 1:\n",
    "                    if count[x-1] == 0:\n",
    "                        if count[x+1] == 0:\n",
    "                            imbalance += 1\n",
    "                    else:\n",
    "                        if count[x+1] != 0:\n",
    "                            imbalance -= 1\n",
    "                res += imbalance\n",
    "            for i in range(left, right - 1):\n",
    "                x = nums[i]\n",
    "                count[x] -= 1\n",
    "                if count[x] == 0:\n",
    "                    if count[x-1] == 0:\n",
    "                        if count[x+1] == 0:\n",
    "                            imbalance -= 1\n",
    "                    else:\n",
    "                        if count[x+1] != 0:\n",
    "                            imbalance += 1\n",
    "                res += imbalance\n",
    "            count[nums[right-1]] -= 1\n",
    "            imbalance -= 1\n",
    "            left += 1\n",
    "            right -= 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumImbalanceNumbers(self, nums: List[int]) -> int:\n",
    "        res = 0\n",
    "        for i, n in enumerate(nums):\n",
    "            ctr = [0] * (max(nums) + 5)\n",
    "            ctr[n] += 1\n",
    "            tmp = 0\n",
    "            for j in range(i + 1, len(nums)):\n",
    "                m = nums[j]\n",
    "                if not ctr[m]:\n",
    "                    if ctr[m - 1] and ctr[m + 1]:\n",
    "                        tmp -= 1\n",
    "                    elif ctr[m - 1] or ctr[m + 1]:\n",
    "                        pass\n",
    "                    else:\n",
    "                        tmp += 1\n",
    "                        \n",
    "                    ctr[m] += 1\n",
    "            \n",
    "                res += tmp\n",
    "            # print(i, n, res)\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumImbalanceNumbers(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        res=0\n",
    "        cnt=Counter()\n",
    "        for i in range(n):\n",
    "            cnt=Counter()\n",
    "            cnt[nums[i]]=1\n",
    "            tmp=0\n",
    "            for j in range(i+1,n): \n",
    "                if cnt[nums[j]]==0:\n",
    "                    tmp-=1\n",
    "                    tmp+=cnt[nums[j]-1]\n",
    "                    tmp+=cnt[nums[j]+1]\n",
    "                cnt[nums[j]]=1\n",
    "                res+=tmp\n",
    "        return -res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumImbalanceNumbers(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        visits = [-1] * (n + 2)\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            #visits = [False] * (n + 2)\n",
    "            #visits[nums[i]] = True\n",
    "            visits[nums[i]] = i\n",
    "            cnt = 0\n",
    "            for j in range(i + 1, n):\n",
    "                #if not visits[nums[j]]:\n",
    "                if visits[nums[j]] != i:\n",
    "                    #cnt += 1 - visits[nums[j] + 1] - visits[nums[j] - 1]\n",
    "                    #visits[nums[j]] = True\n",
    "                    cnt += 1 - (visits[nums[j] + 1] == i) - (visits[nums[j] - 1] == i)\n",
    "                    visits[nums[j]] = i\n",
    "                ans += cnt\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumImbalanceNumbers(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        right = [0] * (n + 1)  \n",
    "        index = [n] * (n + 1)   \n",
    "        for i in range(n - 1, - 1, - 1):\n",
    "            right[i] = min(index[nums[i]], index[nums[i] - 1])\n",
    "            index[nums[i]] = i     \n",
    "        res = 0 \n",
    "        index = [-1] * (n + 1)\n",
    "        for i in range(n):\n",
    "            res += (i - index[nums[i] - 1]) * (right[i] - i)\n",
    "            index[nums[i]] = i \n",
    "        return res - n * (n + 1) // 2 "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumImbalanceNumbers(self, nums: List[int]) -> int:\n",
    "        ans, n = 0, len(nums)\n",
    "        for i, x in enumerate(nums):\n",
    "            vis = [False] * (n + 2)\n",
    "            vis[x] = True\n",
    "            cnt = 0\n",
    "            for j in range(i + 1, n):\n",
    "                x = nums[j]\n",
    "                if not vis[x]:\n",
    "                    cnt += 1 - vis[x - 1] - vis[x + 1]\n",
    "                    vis[x] = True\n",
    "                ans += cnt\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumImbalanceNumbers(self, nums: List[int]) -> int:\n",
    "        ans, n = 0, len(nums)\n",
    "        for i, x in enumerate(nums):\n",
    "            vis = [False] * (n + 2)\n",
    "            vis[x] = True\n",
    "            cnt = 0\n",
    "            for j in range(i + 1, n):\n",
    "                x = nums[j]\n",
    "                if not vis[x]:\n",
    "                    cnt += 1 - vis[x - 1] - vis[x + 1]\n",
    "                    vis[x] = True\n",
    "                ans += cnt\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumImbalanceNumbers(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        res=0\n",
    "        cnt=Counter()\n",
    "        for i in range(n):\n",
    "            cnt=Counter()\n",
    "            cnt[nums[i]]=1\n",
    "            tmp=0\n",
    "            for j in range(i+1,n): \n",
    "                if cnt[nums[j]]==0:\n",
    "                    tmp-=1\n",
    "                    tmp+=(1-cnt[nums[j]-1])\n",
    "                    tmp+=(1-cnt[nums[j]+1])\n",
    "                cnt[nums[j]]=1\n",
    "                res+=tmp\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumImbalanceNumbers(self, nums: List[int]) -> int:\n",
    "        ans,n=0,len(nums)\n",
    "        for i,x in enumerate(nums):\n",
    "            vis=[False]*(n+2)\n",
    "            vis[x]=True\n",
    "            cnt=0\n",
    "            for j in range (i+1,n):\n",
    "                x=nums[j]\n",
    "                if not vis[x]:\n",
    "                    cnt+=1-vis[x-1]-vis[x+1]\n",
    "                    vis[x]=True\n",
    "                ans+=cnt\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "  def sumImbalanceNumbers(self, nums: List[int]) -> int:\n",
    "    n = len(nums)\n",
    "    ans = 0\n",
    "    for i in range(n):\n",
    "      vis = [False] * (n + 2)\n",
    "      vis[nums[i]] = True\n",
    "      count = 0\n",
    "      for j in range(i + 1, n):\n",
    "        x = nums[j]\n",
    "        if not vis[x]:\n",
    "          count += 1 - vis[x - 1] - vis[x + 1]\n",
    "          vis[x] = True\n",
    "        ans += count\n",
    "    return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumImbalanceNumbers(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        #visits = [False] * (n + 2)\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            visits = [False] * (n + 2)\n",
    "            visits[nums[i]] = True\n",
    "            cnt = 0\n",
    "            for j in range(i + 1, n):\n",
    "                if not visits[nums[j]]:\n",
    "                    cnt += 1 - visits[nums[j] + 1] - visits[nums[j] - 1]\n",
    "                    visits[nums[j]] = True\n",
    "                ans += cnt\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumImbalanceNumbers(self, nums: List[int]) -> int:\n",
    "        ans, n = 0, len(nums)\n",
    "        for i, x in enumerate(nums):\n",
    "            vis = [False] * (n + 2)\n",
    "            vis[x] = True\n",
    "            cnt = 0\n",
    "            for j in range(i + 1, n):\n",
    "                x = nums[j]\n",
    "                if not vis[x]:\n",
    "                    cnt += 1 - vis[x - 1] - vis[x + 1]\n",
    "                    vis[x] = True\n",
    "                ans += cnt\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumImbalanceNumbers(self, nums: List[int]) -> int:\n",
    "        ans, n = 0, len(nums)\n",
    "        for i, x in enumerate(nums):\n",
    "            vis = [False] * (n + 2)\n",
    "            vis[x] = True\n",
    "            cnt = 0\n",
    "            for j in range(i + 1, n):\n",
    "                x = nums[j]\n",
    "                if not vis[x]:\n",
    "                    cnt += 1 - vis[x - 1] - vis[x + 1]\n",
    "                    vis[x] = True\n",
    "                ans += cnt\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumImbalanceNumbers(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        res=0\n",
    "        cnt=Counter()\n",
    "        for i in range(n):\n",
    "            cnt=Counter()\n",
    "            cnt[nums[i]]+=1\n",
    "            tmp=0\n",
    "            for j in range(i+1,n):\n",
    "                \n",
    "                if cnt[nums[j]]==0:\n",
    "                    tmp-=1\n",
    "                    if cnt[nums[j]-1]==0 :\n",
    "                        tmp+=1\n",
    "                    if cnt[nums[j]+1]==0:\n",
    "                        tmp+=1\n",
    "                cnt[nums[j]]+=1\n",
    "                res+=tmp\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumImbalanceNumbers(self, nums: List[int]) -> int:\n",
    "        ans, n = 0, len(nums)\n",
    "        vis = [-1] * (n + 2)\n",
    "        for i, x in enumerate(nums):\n",
    "            vis[x] = i\n",
    "            cnt = 0\n",
    "            for j in range(i + 1, n):\n",
    "                y = nums[j]\n",
    "                if vis[y] != i:\n",
    "                    cnt += 1 - (vis[y - 1] == i) - (vis[y + 1] == i)\n",
    "                    vis[y] = i\n",
    "                ans += cnt\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumImbalanceNumbers(self, nums: List[int]) -> int:\n",
    "        from sortedcontainers import SortedList\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            sl = SortedList()\n",
    "            cnt = 0\n",
    "            for j in range(i,n):\n",
    "                x = nums[j]\n",
    "                pos = sl.bisect_left(x)\n",
    "                if 0<pos<len(sl) and sl[pos]-sl[pos-1]>1:\n",
    "                    cnt -= 1\n",
    "                if 0<pos and x-sl[pos-1]>1:\n",
    "                    cnt += 1\n",
    "                if pos<len(sl) and sl[pos]-x>1:\n",
    "                    cnt += 1\n",
    "                ans += cnt\n",
    "                sl.add(x)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumImbalanceNumbers(self, nums: List[int]) -> int:\n",
    "        ans, n = 0, len(nums)\n",
    "        for i, x in enumerate(nums):\n",
    "            vis = [False] * (n + 2)\n",
    "            vis[x] = True\n",
    "            cnt = 0\n",
    "            for j in range(i + 1, n):\n",
    "                x = nums[j]\n",
    "                if not vis[x]:\n",
    "                    cnt += 1 - vis[x - 1] - vis[x + 1]\n",
    "                    vis[x] = True\n",
    "                ans += cnt\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumImbalanceNumbers(self, nums: List[int]) -> int:\n",
    "        ans, n = 0, len(nums)\n",
    "        right = [0] * n\n",
    "        dis = [n] * (n + 1)\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            right[i] = min(dis[nums[i]], dis[nums[i] - 1])\n",
    "            dis[nums[i]] = i\n",
    "        dis = [-1] * (n + 1)\n",
    "        for i, x in enumerate(nums):\n",
    "            ans += (i - dis[x - 1]) * (right[i] - i)\n",
    "            dis[x] = i\n",
    "        return ans - n * (n + 1) // 2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumImbalanceNumbers(self, nums: List[int]) -> int:\n",
    "        ans = 0\n",
    "        n = len(nums)\n",
    "        visited = [-1] * (n+2)\n",
    "\n",
    "        for i , num in enumerate(nums):\n",
    "            visited[num] = i\n",
    "            cnt = 0\n",
    "            for j in range(i+1,n):\n",
    "                if visited[nums[j]] != i:\n",
    "                    visited[nums[j]] = i\n",
    "                    cnt += 1 - int(visited[nums[j]-1] == i) - int(visited[nums[j]+1] == i)\n",
    "                ans += cnt\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "import collections\n",
    "class Solution:\n",
    "    def sumImbalanceNumbers(self, nums: List[int]) -> int:\n",
    "        ###枚举法 时间复杂度O(n2)\n",
    "        n = len(nums)\n",
    "        res = 0\n",
    "        for left in range(n-1):\n",
    "            dic = collections.defaultdict(int)\n",
    "            dic[nums[left]] = True\n",
    "            cnt = 0\n",
    "            for right in range(left+1, n):\n",
    "                if dic[nums[right]]:\n",
    "                    res += cnt\n",
    "                else:\n",
    "                    if dic[nums[right]-1] and dic[nums[right]+1]:\n",
    "                        cnt -= 1\n",
    "                        res += cnt\n",
    "                    elif dic[nums[right]-1] or dic[nums[right]+1]:\n",
    "                        cnt += 0\n",
    "                        res += cnt\n",
    "                    elif dic[nums[right]-1] == False or dic[nums[right]+1] == False:\n",
    "                        cnt += 1\n",
    "                        res += cnt\n",
    "                dic[nums[right]] = True\n",
    "        return res\n",
    "\n",
    "        ###暴力法 时间复杂度O(n3)\n",
    "        # def count_unbalanced(arr: List[int]) -> int:\n",
    "        #     sorted_arr = sorted(arr)\n",
    "        #     count = 0\n",
    "        #     for i in range(len(sorted_arr) - 1):\n",
    "        #         if sorted_arr[i + 1] - sorted_arr[i] > 1:\n",
    "        #             count += 1\n",
    "        #     return count\n",
    "\n",
    "        # n = len(nums)\n",
    "        # result = 0\n",
    "        # for i in range(n):\n",
    "        #     for j in range(i + 1, n + 1):\n",
    "        #         result += count_unbalanced(nums[i:j])\n",
    "        # return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def sumImbalanceNumbers(self, nums: List[int]) -> int:\n",
    "        ans, n = 0, len(nums)\n",
    "        for i, x in enumerate(nums):\n",
    "            vis = [False] * (n + 2)  # 初始化标记数组\n",
    "            vis[x] = True  # 标记当前元素为已访问\n",
    "            cnt = 0  # 初始化不平衡数字数量\n",
    "            \n",
    "            # 内层循环遍历从 i+1 到数组末尾的所有元素\n",
    "            for j in range(i + 1, n):\n",
    "                x = nums[j]\n",
    "                \n",
    "                # 如果该元素没有出现过，那么更新 cnt 并标记该元素为已访问\n",
    "                if not vis[x]:\n",
    "                    cnt += 1 - vis[x - 1] - vis[x + 1]\n",
    "                    vis[x] = True\n",
    "                \n",
    "                # 把 cnt 加到 ans 上\n",
    "                ans += cnt\n",
    "                \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumImbalanceNumbers(self, nums: List[int]) -> int:\n",
    "        ans, n = 0, len(nums)\n",
    "        for i, x in enumerate(nums):\n",
    "            vis = [False] * (n + 2)\n",
    "            vis[x] = True\n",
    "            cnt = 0\n",
    "            for j in range(i + 1, n):\n",
    "                x = nums[j]\n",
    "                if not vis[x]:\n",
    "                    cnt += 1 - vis[x - 1] - vis[x + 1]\n",
    "                    vis[x] = True\n",
    "                ans += cnt\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumImbalanceNumbers(self, nums: List[int]) -> int:\n",
    "        ans, n = 0, len(nums)\n",
    "        right = [0] * n\n",
    "        dis = [n] * (n + 1)\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            right[i] = min(dis[nums[i]], dis[nums[i] - 1])\n",
    "            dis[nums[i]] = i\n",
    "        left = [-1] * n\n",
    "        dis = [-1] * (n + 1)\n",
    "        for i, x in enumerate(nums):\n",
    "            left[i] = dis[x - 1]\n",
    "            dis[x] = i\n",
    "            ans += (i - left[i]) * (right[i] - i)\n",
    "        return ans - n * (n + 1) // 2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumImbalanceNumbers(self, nums: List[int]) -> int:\n",
    "        ans = 0\n",
    "        n = len(nums)\n",
    "        right = [0] * (n+1)\n",
    "        idx = [n] * (n + 1)\n",
    "        for i in range(n-1,-1,-1):\n",
    "            num = nums[i]\n",
    "            right[i] = min(idx[num],idx[num-1])\n",
    "            idx[num] = i\n",
    "\n",
    "        idx = [-1] * (n+1)\n",
    "        for i , num in enumerate(nums):\n",
    "            ans += (i - idx[num-1]) * (right[i] - i)\n",
    "            idx[num] = i\n",
    "        return ans - (n*(n+1)) // 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumImbalanceNumbers(self, nums: List[int]) -> int:\n",
    "\n",
    "        n = len(nums)\n",
    "        if n==1:\n",
    "            return 0 \n",
    "\n",
    "\n",
    "        ans  = 0 \n",
    "        for i in range(n-1):\n",
    "            visited = set([nums[i]])\n",
    "            cnt = 0\n",
    "            for j in range(i+1,n):\n",
    "\n",
    "                if nums[j] not in visited:\n",
    "            \n",
    "                    x = nums[j]\n",
    "                    if x+1 not in visited and x-1 not in visited:\n",
    "                        cnt +=1 \n",
    "                    elif x+1 in visited and x-1 in visited:\n",
    "                        cnt -= 1\n",
    "\n",
    "                ans += cnt \n",
    "                visited.add(nums[j])\n",
    "        return ans \n",
    "                    \n",
    "\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "class Solution:\n",
    "    def sumImbalanceNumbers(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            cur = 0\n",
    "            box = SortedList()\n",
    "            for j in range(i, n):\n",
    "                index = box.bisect_left(nums[j])\n",
    "                if not box:\n",
    "                    box.add(nums[j])\n",
    "                elif index == len(box):\n",
    "                    diff = nums[j] - box[-1]\n",
    "                    if diff > 1:\n",
    "                        cur += 1\n",
    "                    box.add(nums[j])\n",
    "                elif index == 0:\n",
    "                    diff = box[0] - nums[j]\n",
    "                    if diff > 1:\n",
    "                        cur += 1\n",
    "                    box.add(nums[j])\n",
    "                else:\n",
    "                    if box[index] - nums[j] > 1 and nums[j] - box[index-1] > 1:\n",
    "                        cur += 1\n",
    "                    elif box[index] - nums[j] == 1 and nums[j] - box[index-1] == 1:\n",
    "                        cur -= 1\n",
    "                    box.add(nums[j])\n",
    "                # print(i, box, cur, index)\n",
    "                res += cur\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumImbalanceNumbers(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        right = [0] * n\n",
    "        index = [n] * (n + 1)\n",
    "        for i in range(n - 1, - 1, - 1):\n",
    "            right[i] = min(index[nums[i]], index[nums[i] - 1])\n",
    "            index[nums[i]] = i \n",
    "        res = 0\n",
    "        index = [- 1] * (n + 1)\n",
    "        for i in range(n):\n",
    "            res += (right[i] - i) * (i - index[nums[i] - 1])\n",
    "            index[nums[i]] = i \n",
    "        return res - n * (n + 1) // 2 \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumImbalanceNumbers(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        right=[0]*n\n",
    "        idx=[n]*(n+1)\n",
    "        for i in range(n-1,-1,-1):\n",
    "            x=nums[i]\n",
    "            right[i]=min(idx[x],idx[x-1])\n",
    "            idx[x]=i\n",
    "        \n",
    "        ans=0\n",
    "        idx=[-1]*(n+1)\n",
    "        for i,(x,r) in enumerate(zip(nums,right)):\n",
    "            ans+=(i-idx[x-1])*(r-i)\n",
    "            idx[x]=i\n",
    "        return ans-n*(n+1)//2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "class Solution:\n",
    "    def sumImbalanceNumbers(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            sl = SortedList()\n",
    "            sl.add(nums[i])\n",
    "            add = 0\n",
    "            for j in range(i + 1, n):\n",
    "                # print(sl)\n",
    "                # print(len(sl))\n",
    "                idx = sl.bisect(nums[j])\n",
    "                # print(idx)\n",
    "                if idx != 0 and idx != len(sl):\n",
    "                    add -= (sl[idx] - sl[idx - 1] > 1)\n",
    "                if idx != len(sl):\n",
    "                    # print(\"idx\", idx)\n",
    "                    # print(\"nums[i]\", nums[i])\n",
    "                    # print(\"sl[idx] - nums[i]\", sl[idx] - nums[i])\n",
    "                    add += (sl[idx] - nums[j] > 1)\n",
    "                if idx != 0:\n",
    "                    add += (nums[j] - sl[idx - 1] > 1)\n",
    "                sl.add(nums[j])\n",
    "                # print(\"add\", i, j, add)\n",
    "                # print(sl)\n",
    "                res += add\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumImbalanceNumbers(self, nums: List[int]) -> int:\n",
    "        N = len(nums)\n",
    "        left_continue = [None] * N\n",
    "        right_continue = [None] * N\n",
    "        left_larger = [None] * N\n",
    "        right_larger = [None] * N\n",
    "        # Left to right\n",
    "        last_pos = [-1] * (N + 2)\n",
    "        stack = []\n",
    "        for i, v in enumerate(nums):\n",
    "            left_continue[i] = max(last_pos[v], last_pos[v + 1])\n",
    "            while stack and stack[-1][1] <= v:\n",
    "                stack.pop()\n",
    "            if not stack:\n",
    "                left_larger[i] = -1\n",
    "            else:\n",
    "                left_larger[i] = stack[-1][0]\n",
    "            last_pos[v] = i\n",
    "            stack.append((i, v))\n",
    "        del stack[:]\n",
    "        last_pos = [N] * (N + 2)\n",
    "        for i in range(N - 1, -1, -1):\n",
    "            v = nums[i]\n",
    "            right_continue[i] = last_pos[v + 1]\n",
    "            while stack and stack[-1][1] <= v:\n",
    "                stack.pop()\n",
    "            if not stack:\n",
    "                right_larger[i] = N\n",
    "            else:\n",
    "                right_larger[i] = stack[-1][0]\n",
    "            last_pos[v] = i\n",
    "            stack.append((i, v))\n",
    "        ans = 0\n",
    "        for i in range(N):\n",
    "            # left_continue[i] < L <= left_larger[i]\n",
    "            ans += max(left_larger[i] - left_continue[i], 0) \\\n",
    "                    * (right_continue[i] - i)\n",
    "            ans += (i - max(left_larger[i], left_continue[i])) \\\n",
    "                    * max(right_continue[i] - right_larger[i], 0)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumImbalanceNumbers(self, a: List[int]) -> int:\n",
    "        n = len(a) #右a[j] a[j]+1 左 a[j]+1\n",
    "        pre = {j:-1 for j in range(n)} \n",
    "        nex = {j:n for j in range(n)}  \n",
    "        b = {}\n",
    "        for j in range(n):\n",
    "            if a[j]+1 in b:\n",
    "                pre[j] = b[a[j] + 1] \n",
    "            b[a[j]] = j \n",
    "        b = {}\n",
    "        for j in range(n)[::-1]:\n",
    "            if a[j]+1 in b:\n",
    "                nex[j] = min(nex[j], b[a[j] + 1] )\n",
    "            if a[j] in b:\n",
    "                nex[j] = min(nex[j], b[a[j]] )\n",
    "            b[a[j]] = j \n",
    "\n",
    "        ans = 0 - ((1+n)*n//2)\n",
    "        for j in range(n):\n",
    "            ans += (j - pre[j])*(nex[j] - j)\n",
    "        return ans \n",
    "        "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
